The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
We propose algorithms for maintaining two variants of kd-trees of a set of moving points in the plane. A pseudo kd-tree allows the number of points stored in the two children to differ by a constant factor. An overlapping kd-tree allows the bounding boxes of two children to overlap. We show that both of them support range search operations in O(n1/2+∈) time, where ∈ only depends on the...
Range searching, a fundamental problem in numerous applications areas, has been widely studied in computational geometry and spatial databases. Given a set of geometric objects, a typical range query asks for reporting all the objects that intersect a query object. However in many applications, including databases and network routing, input objects are partitioned into categories and a query asks...
We consider the problem of approximating a polygonal curve P under a given error criterion by another polygonal curve P’ whose vertices are a subset of the vertices of P. The goal is to minimize the number of vertices of P’ while ensuring that the error between P’ and P is below a certain threshold. We consider two fundamentally different error measures — Hausdor. and Fréchet error measures. For both...
Let C be a compact set in ℝ2 and let S be a set of n points in ℝ2. We consider the problem of computing a translate of C that contains the maximum number, κ*, of points of S. It is known that this problem can be solved in a time that is roughly quadratic in n. We show how random-sampling and bucketing techniques can be used to develop a near-linear-time Monte Carlo algorithm that computes a placement...
Given a set P of n points in ℝd and an integer k ≥ 1, let w* denote the minimum value so that P can be covered by k cylinders of radius at most w*. We describe an algorithm that, given P and an ɛ > 0, computes k cylinders of radius at most (1 + ɛ)w* that cover P. The running time of the algorithm is O(n log n), with the constant of proportionality depending on k, d, and ɛ. We first show that there...
Given an undirected edge-weighted graph and a depot node, postman problems are generally concerned with traversing the edges of the graph (starting and ending at the depot node) while minimizing the distance traveled. For the Min-Max k-Chinese Postman Problem (MM k- CPP) we have k > 1 postmen and want to minimize the longest of the k tours. We present two new heuristics and improvement procedures...
We describe a new software system SCIL that introduces symbolic constraints into branch-and-cut-and-price algorithms for integer linear programs. Symbolic constraints are known from constraint programming and contribute signi.cantly to the expressive power, ease of use, and e.ciency of constraint programming systems.
In recent years, many theoretically I/O-efficient algorithms and data structures have been developed. The TPIE project at Duke University was started to investigate the practical importance of these theoretical results. The goal of this ongoing project is to provide a portable, extensible, flexible, and easy to use C++ programming environment for efficiently implementing I/O-algorithms and data structures...
In traditional multi-commodity flow theory, the task is to send a certain amount of each commodity from its start to its target node, subject to capacity constraints on the edges. However, no restriction is imposed on the number of paths used for delivering each commodity; it is thus feasible to spread the flow over a large number of different paths. Motivated by routing problems arising in real-life...
In the partial alphabetic tree problem we are given a multiset of nonnegative weights W = w1, . . . , wn, partitioned into k ≤ n blocks B1, . . . , Bk. We want to find a binary tree T where the elements of W resides in its leaves such that if we traverse the leaves from left to right then all leaves of Bi precede all leaves...
We describe and analyze empirically an implementation of some generalizations of Dijkstra’s algorithm for shortest paths in graphs. The implementation formed a part of the TRANSIMS project at the Los Alamos National Laboratory. Besides offering the first implementation of the shortest path algorithm with regular language constraints, our code also solves problems with time-dependent edge delays in...
We study the problem of maintaining a dynamic ordered set subject to insertions, deletions, and traversals of k consecutive elements. This problem is trivially solved on a RAM and on a simple two-level memory hierarchy. We explore this traversal problem on more realistic memory models: the cache-oblivious model, which applies to unknown and multi-level memory hierarchies, and sequential-access models,...
In the Order-Maintenance Problem, the objective is to maintain a total order subject to insertions, deletions, and precedence queries. Known optimal solutions, due to Dietz and Sleator, are complicated. We present new algorithms that match the bounds of Dietz and Sleator. Our solutions are simple, and we present experimental evidence that suggests that they are superior in practice.
We consider the problem of laying out a tree or trie in a hierarchical memory, where the tree/trie has a fixed parent/child structure. The goal is to minimize the expected number of block transfers performed during a search operation, subject to a given probability distribution on the leaves. This problem was previously considered by Gil and Itai, who show optimal but high-complexity algorithms when...
We give an exact geometry kernel for conic arcs, algorithms for exact computation with low-degree algebraic numbers, and an algorithm for computing the arrangement of conic arcs that immediately leads to a realization of regularized boolean operations on conic polygons. A conic polygon, or polygon for short, is anything that can be obtained from linear or conic halfspaces (= the set of points where...
In TSP with neighborhoods we are given a set of objects in the plane, called neighborhoods, and we seek the shortest tour that visits all neighborhoods. Until now constant-factor approximation algorithms have been known only for cases where the objects are of approximately the same size. We present the first polynomial-time constant-factor approximation algorithm for disjoint convex fat objects of...
Analysis of genomes evolving by inversions leads to a general combinatorial problem of Sorting by Reversals, MIN-SBR, the problem of sorting a permutation by a minimum number of reversals. Following a series of preliminary results, Hannenhalli and Pevzner developed the first exact polynomial time algorithm for the problem of sorting signed permutations by reversals, and a polynomial time algorithm...
A radio labeling of a graph G is an assignment of pairwise distinct, positive integer labels to the vertices of G such that labels of adjacent vertices differ by at least 2. The radio labeling problem (RL) consists in determining a radio labeling that minimizes the maximum label that is used (the so-called span of the labeling). RL is a well-studied problem, mainly motivated by frequency assignment...
In the test cover problem a set of items is given together with a collection of subsets of the items, called tests. A smallest subcollection of tests is to be selected such that for every pair of items there is a test in the selection that contains exactly one of the two items. This problem is NP-hard in general. It has important applications in biology, pharmacy, and the medical sciences, as well...
Given a set S of n points in the plane, we give an O(n log n)- time algorithm that constructs a plane t-spanner for S, with t ≈ 10.02, such that the degree of each point of S is bounded from above by 27, and the total edge length is proportional to the weight of a minimum spanning tree of S. These constants are all worst case constants that are artifacts of our proofs. In practice, we believe them...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.